1. Introduction
The present invention relates generally to the field of digital image steganography and is more particularly directed to a new system of steganography referred to herein as Spread Spectrum Image Steganography (SSIS). Steganography, meaning xe2x80x9ccovered writingxe2x80x9d in Greek, is the science of communicating in a manner such that the existence of the communication is hidden. The SSIS system hides and recovers a message of substantial length within digital imagery while maintaining the original image size and dynamic range. The hidden message can be recovered using appropriate keys without any knowledge of the original image. A message embedded by the SSIS method can be in the form of text, imagery or any other digital signal. Applications for such a data hiding scheme include in-band captioning, covert communication, image tamperproofing, authentication, embedded control and revision tracking.
2. Discussion of Related Art
In this application several publications are referenced by Arabic numerals in brackets { }. Full citations for these publications may be found at the end of the written description immediately preceding the claims. The disclosures of all such publications, in their entireties, are hereby expressly incorporated by reference in this application as if fully set forth, for purposes of indicating the background of the invention and illustrating the state of the art.
Humans have been engaged in steganography for thousands of years. There are several examples of steganography from ancient Greece {1}. One of the first is from the Histories of Herodotus. In ancient Greece, text was written on wax covered tablets. In one story Demeratus wanted to notify Sparta that Xerxes intended to invade Greece. To avoid capture, he scraped the wax off of the tablets and wrote a message on the underlying wood. He then covered the tablets with wax again. The tablets appeared to be blank and unused so they passed inspection by sentries without question. Another method was to shave the head of a messenger and tattoo a message or image on the messenger""s head. After allowing his or her hair to grow, the message would be undetected until the head was shaved again.
Modern times have yielded more advanced techniques, such as the use of invisible inks, where certain chemical reactions are necessary to reveal the hidden message. Common sources for invisible inks are milk, vinegar and fruit juices. All of these darken when heated. Another method employs routine correspondencexe2x80x94applying pin pricks in the vicinity of particular letters can spell out a secret message. As message detection improved, new technologies developed that permitted the passage of greater information that was better hidden. Advances in photography produced microfilm which was used to transmit messages via carrier pigeon. Improved film and lenses permitted reduction in the size of a full typewritten page to that of a printed period. This technique, known as the microdot, was used by the Germans in World War II.
With much of today""s communications occurring electronically, digital signals increasingly are used as vehicles for steganographic communication. These signals, which typically represent audio, video or still imagery, are defined as cover signals. Schemes where the unaltered cover signal is needed to reveal the hidden information are known as cover escrow schemes. They can be useful in traitor tracing schemes such as those described in {2}. In this scenario, copies of the cover signal are disseminated with the identity of the assignee embedded within, resulting in a modified cover signal. If unauthorized copies of the signal are acquired, the source of the copy is established by subtracting the original cover data from the modified signal, thereby exposing the offender""s identity. However, in many applications it is not practical to require possession of the unaltered cover signal in order to extract the hidden information. More pragmatic methods, known as blind or oblivious schemes, have the ability to reveal the embedded data from the modified signal without using the cover. Strategies such as these are predominant among steganographic schemes of the present day.
Digital steganography is currently a very active research area encompassing methods of copyright protection, image authentication, and secure communications. Several techniques are known that conceal information in the least significant bit (LSB) plane of digital images. This manipulation may take many forms, from direct replacement of the cover LSBs with message bits to some type of logical or arithmetic combination between the two, such as the xe2x80x9cexclusive orxe2x80x9d operation. By modifying the insignificant bits, the cover image is typically altered in a nearly imperceptible manner thereby ensuring that any observer would be unaware of the presence of the hidden information {3}. Other techniques that utilize the LSB method incorporate the alteration of color pallets for images stored in the GIF format {4} or the use of m-sequences by Wolfgang and Delp {5}. There have been numerous software programs written that apply this concept to different image formats {6}. Employing the LSB technique for data hiding achieves both invisibility and reasonably high storage payload, a maximum of one bit per pixel (bpp) for grayscale and three bpp for Red-Green-Blue (RGB) images. However, the method is vulnerable and the hidden information is subject to extraction by undesirable parties. In some cases this technique requires cover image escrow of the LSB plane for message recovery. Moreover, LSB methods are generally not resilient to noisy transmission because the subject bits must be transmitted in an error free manner for reliable message decoding.
There are, of course, many cover escrow approaches, i.e., schemes where it is necessary to possess the original cover signal in order to retrieve the hidden information. Such a method was proposed by Cox, et al. {7}, where the message is inserted into the most significant Discrete Cosine Transform (DCT) coefficients of the cover image using techniques analogous to spread spectrum, thus allowing the hidden signal to be imperceptible. Other cover escrow schemes can be found in {8} and {9}.
Several procedures for data hiding in imagery and audio can be found in {10}. One, entitled Patchwork, embeds a specific statistic within the cover image. First, pairs of image regions are selected using a pseudorandom number generator. Pseudorandom is defined as random in appearance but reproducible by deterministic means, such as a number generated by a series of equations. Once a pair is selected, the pixel intensities within one region are increased by a constant value while the pixels of the other region decreased by the same value. A texture mapping method is also described which copies areas of random textures from one area of the image to another. Simple autocorrelation of the signal is used to expose the hidden information. The payload in both of these schemes is low.
A few methods have been proposed which exploit characteristics of the human visual system to make the embedded data less perceptible. Recent research in this area was performed by Swanson, Zhu and Tewfik {11} where both spatial and frequency masking techniques are presented. This method exploits the claim that audio or visual signals may become invisible in the presence of another signal known as a masker {12}. The payload of this system is naturally cover image dependent and not quantified.
Embedding data using the statistical properties of dithered imagery was proposed by Tanaka, et al. {13}. This systems accommodates two and three kilobytes of hidden information into bilevel and three level 256xc3x97256 images, respectively.
A few patents exist in this area of research. U.S. Pat. No. 4,939,515 to Adelson suggests using a digital signal to specify the quantizer used to digitize an analog waveform. The choice of the quantizer corresponds to the hidden information. A familiar steganographic patent is U.S. Pat. No. 5,636,292 to Rhoads which uses the Digimarc watermarking scheme to hide an N-bit sequence using N pseudorandom patterns. There is of course an upper limit on N which reflects low payload. In addition, U.S. Pat. No. 5,613,004 to Cooperman discusses a concept to hide information in the frequency domain of an audio or imagery signal using a cipher technique to hide a signature. This signature is also short in length.
As has been demonstrated, all of the foregoing methods suffer from various drawbacks. What is needed is a reliable, undetectable method of digital steganography that can hide messages of significant size in cover signals while still maintaining the quality of the cover signal and without requiring prior knowledge of the original cover signal for decoding.
It is an object of this invention to provide a method of data hiding and secret communication that maximizes the amount of data successfully hidden and is capable of being decoded without prior knowledge of the original cover signal and without errors. The above and other objects are achieved, at least in part, by providing a method of steganography for concealing message within digital signals comprising encoding an input message with an error correcting code to produce an encoded message, generating a spreading sequence with a pseudorandom noise generator according to a key, modulating the encoded message by the spreading sequence to produce an embedded signal and combining the embedded signal with a cover signal to produce a stegosignal in which the input message is embedded. Preferably, the embedded signal is interleaved to enhance recovery of the embedded signal. In accordance with one aspect of the invention, interleaving is performed according to a key. In accordance with another aspect of the invention, the stegosignal is quantized to preserve the original dynamic range of the cover signal. In accordance with another aspect of the invention the low error rate control coding may comprise a binary expansion of a Reed-Solomon code. In accordance with another aspect of the invention, the input message of the SSIS system is encrypted with a key. In accordance with a preferred embodiment of the invention, the cover signal is a digital image.
In accordance with another aspect of the invention decoding of the steganographic messages embedded within digital signals include restoring the digital signal with a restoration filter to produce a restored digital signal, subtracting the restored digital signal from the digital signal to produce a difference signal, deinterleaving the difference signal according to a key, replicating a pseudorandom spreading sequence according to a key, demodulating the deinterleaved signal with the spreading sequence to construct an estimate of the message and decoding the message with an error correcting code to produce a decoded message. In accordance with another aspect of the invention, the decoder also decrypts the decoded message with a key.